package cn.com.leetcode.divideandconquer;

/**
 * 数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
 * <p>
 * 示例 1：
 * <p>
 * 输入：[1,2,5,9,5,9,5,5,5]
 * 输出：5
 *  
 * <p>
 * 示例 2：
 * <p>
 * 输入：[3,2]
 * 输出：-1
 *  
 * <p>
 * 示例 3：
 * <p>
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-majority-element-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo_Ms17_10 {
    public static void main(String[] args) {
        Demo_Ms17_10 demo_ms17_10 = new Demo_Ms17_10();
        int[] nums = {2,2,1,1,1,2,2};
        int majorityElement = demo_ms17_10.majorityElement(nums);
        System.out.println(majorityElement);
    }

    public int majorityElement(int[] nums) {
        int mode = 0;
        int count = 0;
        int length = nums.length;
        for (int num : nums) {
            if (count == 0) {
                mode = num;
            }
            if (mode == num) {
                count++;
            } else {
                count--;
            }
        }

        int modeCount = 0;
        int t = length / 2 + 1;
        for (int num : nums) {
            if (num == mode) {
                modeCount++;
            }

            if (modeCount >= t) {
                return mode;
            }
        }
        return -1;
    }


}
